package com.guaoran.algorithm.binary.tree;

import com.guaoran.algorithm.common.CommonUtil;
import com.guaoran.algorithm.entity.TreeNode;

import java.util.List;

/**
 * @author : 孤傲然
 * @description : 最小公共祖先
 * https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
 * @date :2021/1/21 22:18
 */
public class LowestCommonAncestorOfABinaryTree {
    public static void main(String[] args) {
        TreeNode treeNode = CommonUtil.createTreeNode(new Integer[]{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4});
        TreeNode treeNode2 = CommonUtil.createTreeNode(new Integer[]{1,2});
        List<TreeNode> treeNodes = CommonUtil.readTreeNode(treeNode);
        System.out.println(treeNodes);
        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(4);
        System.out.println(lowestCommonAncestor(treeNode, p, q));
        System.out.println(lowestCommonAncestor(treeNode2, new TreeNode(1), new TreeNode(2)));
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null || root.val == p.val || root.val == q.val){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){
            return root;
        }
        if(left != null){
            return left;
        }
        if(right != null){
            return right;
        }
        return null;
    }
}
